package airthmetic.exercise.sort.cmp;


import java.util.Random;

// 快速排序
public class _912_排序数组_Quick2 {

    public int[] sortArray(int[] nums) {
        if(nums == null || nums.length < 2){
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort(int[] nums, int left, int right){
        // terminal
        if(left >= right){
            return;
        }
        int position = partition(nums,left,right);
        quickSort(nums,left, position-1);
        quickSort(nums,position+1, right);
    }

    Random rondow = new Random();
    public int partition(int[] nums, int left, int right){
        int pivot = rondow.nextInt((right - left) + 1) + left;
        swap(nums, left, pivot);
        int targetNum = nums[left];
        int i = left+1;
        int j = right;
        while(true){
            while(i <=right && nums[i] < targetNum){
                i++;
            }
            while(j> left && nums[j] > targetNum){
                j--;
            }

            if(i>=j){
                break;
            }
            swap(nums,i,j);
            i++;
            j--;
        }

        swap(nums,j,left);
        return j;

    }

    public void swap(int[] nums, int left, int right){
        if(left == right){
            return;
        }
        nums[left] ^= nums[right];
        nums[right] ^= nums[left];
        nums[left] ^= nums[right];
    }
}
